package org.HashTable;
/*
    哈希表
    给每份数据分配一个编号，放入表格（数组）
    建立编号与表格索引的关系，将来就可以通过编号快速查找数据
      1.理想情况编号唯一，表格能容纳所有数据
      2.显示是不能说为了容纳所有数据造一个超大表格，编号也有可能重复

    解决
      1.有限长度的数组，以【拉链】方式存储数据
      2.允许编号适当重复，通过数据自身来进行区分
 */


public class HashTable {
    //哈希节点
    public class Entry{
        public int hash;   //哈希码
        public Object key;    //键
        public Object value; //值
        public Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    public Entry[] table = new Entry[16];
    public int size = 0;   //元素个数
    float loadFactor = 0.75f;
    int threshold = (int) (loadFactor * table.length);

    /*  求模运算替换为位运算
         -  前提：数组长度是 2 的 n 次方
         -  hash % 数组长度 等价于 hash & （数组长度-1）
     */

    //根据 hash 码获取 value
    public Object get(int hash,Object key){
        int index = hash & (table.length - 1);
        if (table[index] == null){
            return null;
        }
        Entry front = table[index];
        while (front != null){
            if (front.key.equals(key)){
                return front.value;
            }
            front = front.next;
        }
        return null;
    }

    //向 hash 表存入新 key value ，如果 key 重复，则更新 value
    public void put(int hash,Object key, Object value){
        int index = hash & (table.length - 1);
        if (table[index] == null){
            // 1.index 处有空位，直接新增
            table[index] = new Entry(hash,key, value);
        }else {
            //2.index 处无空位，沿链表查找，有更新，无新建
            Entry p = table[index];
            while (true){
                if (p.key.equals(key)){
                    p.value = value;
                    return;
                }
                if(p.next == null){
                    break;  //防止最后一个key相等
                }
                p = p.next;
            }
            p.next = new Entry(hash,key,value);
        }
        size ++;
        if (size >= threshold){
            resize();
        }
    }

    private void resize() {
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length;i++){
            Entry p = table[i];
            if (p != null){
                /*
                    拆分链表，移动到新的数组，拆分规律
                    * 一个链表最多拆成两个
                    * hash & table.length == 0 的一组
                    * hash & table.length != 0 的一组
                 */
                Entry a= null;
                Entry b= null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null){
                    if ((p.hash & table.length) != 0){
                        if (a != null){
                            a.next = p;
                        }else {
                            aHead = p;
                        }
                        //分配到a
                        a = p;
                    }else {
                        if (b != null){
                            b.next = p;
                        }else {
                            bHead = p;
                        }
                        //分配到b
                        b = p;
                    }
                    p = p.next;
                }
                // 规律：a链表保持索引不变，b链表索引位置+table。length
                if (a != null){
                    newTable[i] = aHead;
                }
                if (b != null){
                    newTable[i + table.length] = bHead;
                }
            }
        }
    }

    //根据 hash 码删除，返回删除的value
    public Object remove(int hash, Object key){
        int index = hash & (table.length - 1);
        Entry p = table[index];
        Entry parent = null;
        // 1. 搜索的hash值下无数据
        if(p == null){
            return null;
        }
        while (p != null){
            if(p.key.equals(key)){
                if(parent == null){
                    // 2. 该hash值下的第一个值就是删除值
                    table[index] = p.next;
                }else {
                    // 3. 查找后面当中符合的删除值
                    parent.next = p.next;
                }
                size--;
                return p.value;
            }
            parent = p;
            p = p.next;
        }
        return p;
    }


    public Object get(Object key) {
        int hash = key.hashCode();
        return get(hash, key);
    }

    public void put(Object key, Object value){
        int hash = key.hashCode();
        put(hash, key, value);
    }

    public  Object remove(Object key){
        int hash = key.hashCode();
        return remove(hash,key);
    }

    public static void main(String[] args) {
        System.out.println(7 & 9);
    }
}
